package mo.offer_version2;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 需要考虑不可达的位置
 */
public class L13 {

    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[m][n];
        queue.add(new int[]{0, 0});
        visited[0][0] = true;
        int ret = 1;
        int[] dx = new int[]{1, 0};
        int[] dy = new int[]{0, 1};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 2; i++) {
                int tx = cur[0] + dx[i];
                int ty = cur[1] + dy[i];
                if (tx >= 0 && tx < m && ty >=0 && ty < n && !visited[tx][ty] && (get(tx) + get(ty) <= k)) {
                    ret++;
                    queue.offer(new int[]{tx, ty});
                    visited[tx][ty] = true;
                }
            }
        }
        return ret;
    }

    private int get(int coordinate) {
        int x = 0;
        while (coordinate != 0) {
            x += (coordinate % 10);
            coordinate = coordinate / 10;
        }
        return x;
    }

    public static void main(String[] args) {
        L13 test = new L13();
        System.out.println(test.movingCount(16, 8, 4));
    }

}
